There are many cases encountered in which in order to establish a system for supplying information to a previously determined group, a key (group key) is distributed only to a subscriber enrolled as a member of the group and then cryptographic communication through a key is performed. The cryptographic technique is useful in many applications such as distribution of contents to a portable telephone, decipherer/reproducer of a DVD player, distribution of software via CDROM interface, police radio communication and local communication between groups in P2P service.
In the system described above, in the event a part of a terminal device (decoder) is removed away such as in a theft attempt, it is in danger of leakage of a group key to an unauthorized person other than members of the group. For this reason, the used group key has to be updated to create a new key and the new key has to be shared by the members of the group as quickly as possible.
A technique of updating a key has an extremely important role in a system that utilizes a once-established infrastructure for a long period of time.
Assume that in this type of system (hereinafter, refer to as a broadcasting type cryptographic communication system) consisting of a plurality of subscriber terminals, messages are distributed to all subscriber terminals excluding a single subscriber terminal or a plurality of subscriber terminals. Note that the term “exclude” means operation for excluding a certain subscriber terminal (or certain subscriber terminals) from a group and that the excluded subscriber terminal is referred to as “a terminal to be excluded,” (hereinafter, refer to as a exclusion-target terminal). In general, when excluding an exclusion-target terminal, it is required to distribute a new group key to each of the individual subscriber terminals other than the exclusion-target terminal. For this reason, as the scale of a group increases, the amount of communication and the amount of time delay required to complete operation for making all the subscriber terminals share a new group key increase.
Conventionally, in order to reduce the above-described amount of time delay required to update the groups key, a variety of techniques have been conceived. A technique (a first conventional technique) disclosed in Japanese Patent Application 2000-196581 is exemplified as a conventional technique of the above-stated type.
The first conventional technique disclosed in the above-stated publication employs an algorithm that makes the amount of communication and the amount of time delay after determination of an exclusion-target terminal not proportional to the number “n” of subscribers as a member of the group. When employing the above-described algorithm and assuming that the maximum number of terminals to be excluded is “k,” a number, proportional to “k,” of modular exponentiation operations have to be performed by each of the subscriber terminals to calculate the group key. Accordingly, if “k” is far smaller than “n” (k<<n), key distribution according to this technique can be made far more effectively than a general distribution of group key. For instance, when assuming that a system (n=10,000) includes 10,000 subscriber terminals and the number of terminals to be excluded is 100 (k=100), although the general distribution of group key needs processing to be performed a number of times proportional to the number “10,000,” key distribution according to the first conventional technique disclosed in the publication needs processing to be performed a number of times proportional to the number “100.”
However, in a system (e.g., a system for providing services to mobile terminals such as a portable telephone) including up to some million subscriber terminals and in a similar system, it is required to make the number “k” that represents the maximum number of terminals to be excluded enlarged (e.g., some thousands to some ten thousands) to meet the scale of a group. This makes computation load on a terminal that is poor in its computing ability become considerable, which load is imposed by decryption and is proportional to the number “k.” Therefore, it is desirable to perform group key distribution that needs decryption to be performed a number of times not proportional to the number “k,” or, if possible, a constant number of times.
Japanese Patent Application 2001-203682 is exemplified as a conventional technique (second conventional technique) to solve the above-described problems.
The second conventional technique disclosed in the publication realizes decryption by performing modular exponentiation operations only “2” times without depending on the number “n,” which represents the total number of subscriber terminals, and the number “k,” which represents the maximum number of terminals to be excluded. Accordingly, the second conventional technique allows a system including a very large number of subscriber terminals to make quick distribution of a group key.
In a broadcasting type cryptographic communication system, members of a protocol are defined as follows.
Key distribution server: A reliable agency for determining system parameters at the time of setup and distributing personal keys to individual subscriber terminals. When going to distribute a group key, the server determines which subscriber terminals are to be excluded and then distributes the group key through broadcast. The key distribution server is denoted by “S.”
Subscriber terminal: A terminal for receiving a broadcast material from the key distribution server. A subscriber terminal “i” receives a personal key “si” from the key distribution server at the time of setup. A set of subscriber terminals is defined as a set Φ={1, . . . , n} (n=|Φ| represents the total number of subscriber terminals).
Subscriber terminal excluded: A subscriber terminal being excluded by the key distribution server. A set of “d” (<k) subscriber terminals to be excluded when the key distribution server distributes a group key in a first round is defined as a subset Λl (⊂ Φ). Once being excluded, the subscriber terminal is not able to decrypt a group key after the round in which the terminal is excluded and therefore, is never repeatedly excluded in a plurality of rounds. That is, the intersection of two sets, Λl∩Λl′={0} (l≠l′). Furthermore, assume that the number, which represents the total number of excluded subscriber terminals, never exceeds the number “k” throughout the rounds (i.e., |∪Λl|≦k).
Effective subscriber terminal: A subscriber terminal being not excluded. Assume that a set of subscriber terminals effective in the first round of distribution of group key is defined as a set Ω1 (=Φ\U1j=1Λj).
In the broadcasting type cryptographic communication system thus defined, U1 is distributed to the effective subscriber terminals Ω1 among the entire subscriber terminals Φ in the first round. Encrypting messages using U1 allows a cryptographic communication of the type used for broadcasting within the group Ω1. That is, the cryptographic communication is performed as follows.
1. Let Ω0=Φ. The key distribution server distributes a group key “U0” and a personal key keyi to each subscriber “i” (i ∈ Φ) through a point-to-point and key distribution protocol connection.
2. For each of l≧1, the following processings are repeatedly performed (hereinafter, performing the following processings one time is referred to as “l round”).                (a) Key distribution server determines Λl ⊂ Ωl−1.        (b) If k≧Σ1j=l|Λj|, Φ:=Ωl−1, U0:=Ul−1 and then return to 1.        (c) Key distribution server distributes a header Hl to Ωl to make Ωl calculate Ul.        (d) v ∈ Ωl calculates Ul using Hl and keyv.        (e) Key distribution server and Ωl perform broadcasting type cryptographic communication using Ul.        
Furthermore, in the description hereinafter set forth, the following parameters are employed. “p” and “q” are a large prime number satisfying q|p−1 and “g” is an element of the order “q” on finite field Zp. The size of “p” and “q” is determined so that discrete logarithm problems on a group GF(q), which group consists of “g” as a generating element, becomes computationally difficult. In the following explanation, unless otherwise noted, calculations are all made using modulo p arithmetic. Note that though not described in detail, order “p” can be defined on arbitrary group GF(p) so that solving a discrete logarithm problem becomes computationally difficult, in addition to the definition different from that used in defining order “p” at a prime on group GF(q). For instance, a group constructed by (1) making multiplication operations on an element of order “p” correspond to addition operations on curves such as an elliptical curve on an arbitrary finite field or (2) by letting a prime number “p′” be an exponent instead of a prime number “p” and then performing arithmetic operations on an extension field GF(p′) instead of performing remainder operations using a prime number “p′” as a modulus.
E (key, message) indicates message encryption that uses symmetric key encryption. “n” denotes the total number of subscriber terminals and “k” (k<n) denotes the maximum number of terminals to be excluded.
Under the above-described assumption, the broadcasting type cryptographic communication system is required to satisfy the following four requirements in terms of security and efficiency.
1. An effective subscriber terminal v ∈ Ωl is able to independently decrypt a group key U1 (in polynomial time).
2. Even when using a personal key that each of the “k” excluded subscriber terminals owns, any person cannot decrypt a group key (in probabilistic polynomial time) after the round in which the subscriber terminals are excluded.
3. The length of a header used in distribution of group key and the size of personal key that each subscriber terminal owns do not depend on the number that represents the total number of subscriber terminals.
4. When a number of modular exponentiation operations are performed over a time interval over which the header is received to calculate the group key and the decryption of group key (decryption) is completed, the number does not depend on “n” and “k.”
The requirement 1 is a requirement requiring that a subscriber terminal effectively be able to independently perform decryption. In a broadcasting type cryptographic communication system, it is important not to place additional traffic on the network when the subscriber terminal needs not to communicate with other terminals upon decryption.
The requirement 2 is a requirement that has to be satisfied to prevent an excluded subscriber terminal from trying to decrypt a session key in conspiracy with other excluded terminals.
The requirement 3 is a requirement that has to be satisfied to prevent significant increase in the amount of processing when the system includes a very large number of subscriber terminals.
The requirement 4 is a requirement that has to be satisfied to decrypt a group key requiring an amount of processing, which amount does not depend on “n” and “k,” when “k” needs to be determined large in proportion to the scale of a large group.
So-called “Spare Shadow Attack” and “r publish attack” are included in the requirement 2. A protocol using a time threshold essentially cannot address the problem caused by “Secret Publish Attack.” Not that when assuming the number of attackers who reveal a secret is “w,” if the number of unauthorized persons is not greater than “k-w,” security can be maintained. Accordingly, evaluating the security of protocol under the condition that the total number of unauthorized subscriber terminals, which are in conspiracy with other unauthorized subscriber terminals, is not greater than “k” allows discussion about security within the same field as that of the requirement 2.
The aforementioned conventional technique 1 satisfies the above-stated requirements 1, 2 and 3. The length of an encrypted message to be distributed corresponds to a constant time interval O(k) and the size of a personal key to be distributed corresponds to O(l), meaning that those factors produce extreme efficiency. However, since the number, which represents the number of modular exponentiation operations to be performed to decrypt a group key, equals to O(k) and further, the modular exponentiation operations cannot be placed in pre-calculation prior to reception of the group key, the conventional technique 1 does not satisfy the requirement 4.
The conventional technique 2 focuses its attention on the necessity for the requirement 4 and then provides an algorithm that satisfies the requirement 4. However, the conventional technique 2 does not satisfy the requirement 2, which is most important in terms of security, for the reason resulting from the following analysis. That is, when a group key is distributed finite times, the subscriber terminals being not excluded is able to require secret information about an entire system and further to cancel excluding operation to be performed after the key is distributed finite times (e.g., if k≧5, an attack on the system is possible after the group key is distributed three times).
How the conventional technique 2 does not satisfy the requirement 2 will be shown below. First, the algorithm that the conventional technique 2 employs for a broadcasting type cryptographic communication will be explained.
1. Setup
A key distribution server determines the number “k” that represents the maximum number of terminals to be excluded and randomly selects a kth degree polynomial Zq represented by the following numerical expression 1.
                                          F            ⁡                          (              x              )                                =                                    ∑                              j                =                0                            k                        ⁢                                          a                j                            ⁢                              x                j                                                    ⁢                                  ⁢                              G            ⁡                          (              x              )                                =                                    ∑                              j                =                0                            k                        ⁢                                          b                j                            ⁢                              x                j                                                                        [                  Numerical          ⁢                                          ⁢          expression          ⁢                                          ⁢          1                ]            
F(0)=S and G(0)=T(mod q) are secret keys that only the key distribution server knows. The key distribution server distributes keyi=(si, fi)=(F(i), gG(i)/F(i)) (i=1, . . . n) to each subscriber terminal “i” via a secret communication path. In addition, the key distribution server randomly selects an element U0 ∈ GF(q) and broadcasts the same.
2. Encryption of Group Key
The group key Ul to be distributed in the “l” (≧1) round is distributed in the following manner. Randomly select an element rl ∈ Zq and determine Xl=grl. Then, determine a set Λl for “d” subscriber terminals to be excluded. Select “(k-d)” pieces of integers from between “n+k(R−l)” and “n+kR,” and determine a set Θ1 consisting of the “(k−d)” pieces of integers. The key distribution server determines Ml1, . . . , Mlk based on the following numerical expression 2.
[Numerical expression 2]Mij=rlF(j)+G(j)mod q(j∈Λl∪Θl)
Finally, the key distribution server determines E (Ul-1, Bl)=E(Ul-1, Xl∥[(j, Mlj)|j ∈ Λl ∪ Θl]) and then broadcasts the same. The group key that is shared in the “l” round is Ul=grlS+T.
3. Decryption of Group Key
Since the effective subscriber terminal, i.e., an element v ∈ Ωl, in the “l” round is an element v ∈ Ωl-1, the subscriber terminal obtains Ul-1 in the round “l-1.” The subscriber terminal “v” decrypts Bl in the received encrypted message E (Ul-1, Bl) using Ul-1. Then, using the information about Bl, the terminal calculates the group key Ul based on the numerical expression 3.
[Numerical Expression 3]Ul=(Xlfv)Wl1gWl2 where,
                                          W                          l              ⁢                                                          ⁢              1                                =                                    s              v                        ⁢                          L              ⁡                              (                v                )                                      ⁢            mod            ⁢                                                  ⁢            q                          ⁢                                  ⁢                              W                          l              ⁢                                                          ⁢              2                                =                                    ∑                              j                ∈                                                      Λ                    l                                    ⁢                                      Θ                    l                                                                        ⁢                                          (                                                      M                    lj                                    ⁢                                      L                    ⁡                                          (                      j                      )                                                                      )                            ⁢              mod              ⁢                                                          ⁢              q                                                          [                  Numerical          ⁢                                          ⁢          expression          ⁢                                          ⁢          4                ]            
Furthermore, L(j) is an interpolation coefficient given by Lagrange polynomial, represented by the following numerical expression 5.
                              L          ⁡                      (            j            )                          =                              ∏                          t              ∈                                                Λ                  l                                ⋃                                  Θ                  l                                ⋃                                                      {                    v                    }                                    /                                      {                    j                    }                                                                                ⁢                                    t              /                              (                                  t                  -                  j                                )                                      ⁢            mod            ⁢                                                  ⁢            q                                              [                  Numerical          ⁢                                          ⁢          expression          ⁢                                          ⁢          5                ]            
Subsequently, how the algorithm employed in the conventional technique 2 does not satisfy the requirement 2 will be shown. How the effective and optional subscriber terminal ∀v, i.e., an element ∀v ∈ ΩR, in the “R” round calculates and determines the secret information “S” and “T” that only the key distribution server should know will be shown in detail. The terminal “v” obtains (j, Mlj) (l=1, . . . , R, j =1, . . . , k) in the rounds 1 to R and the obtained (j, Mlj) satisfies the relationship represented by the following numerical expression 6.
                              M          ij                =                                            r              l                        ⁢                                          ∑                                  i                  =                  0                                k                            ⁢                                                a                  t                                ⁢                                  j                  t                                                              +                                    ∑                              i                =                0                            k                        ⁢                                          b                t                            ⁢                              j                t                            ⁢              mod              ⁢                                                          ⁢                              q                ⁡                                  (                                                            l                      =                      1                                        ,                    …                    ⁢                                                                                  ,                    R                    ,                                          j                      ∈                                                                        Λ                          l                                                ⋃                                                  Θ                          l                                                                                      ,                                                                                                                                                Λ                            l                                                    ⋃                                                      Θ                            l                                                                                                                      =                      k                                                        )                                                                                        [                  Numerical          ⁢                                          ⁢          expression          ⁢                                          ⁢          6                ]            
Note that since “j” is known, the “kR” pieces of equations are obtained for “2k+2+R” pieces of variables, a0, . . . , ak, b0, . . . , bk, r1, . . . , rR. That is, when “R” satisfies the following numerical expression 7, all the secret keys, i.e., “S” (=a0) and “T” (=b10), that the key distribution server owns can be calculated.
                                                        2              ⁢              k                        +            2            +            R                    ≤                      k            ⁢                                                  ⁢            R                          ⇔                  R          ≥                                    2              ⁢                              (                                  k                  +                  1                                )                                                    k              -              1                                                          [                  Numerical          ⁢                                          ⁢          expression          ⁢                                          ⁢          7                ]            
For instance, if k≧5, all the effective subscriber terminals can calculate in the 3 round the secret key (such as “S” and “T”) that the key distribution server owns. This indicates that the conventional technique 2 does not satisfy the requirement 2.